package StringSecond.SwordOffer;

public class CountSubstrings {
    /**
     * 剑指 Offer II 020. 回文子字符串的个数
     * 给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。
     * <p>
     * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * 输入：s = "abc"
     * 输出：3
     * 解释：三个回文子串: "a", "b", "c"
     * 示例 2：
     * <p>
     * 输入：s = "aaa"
     * 输出：6
     * 解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"
     */

    //动态规划
    public static int countSubstrings(String s) {
        int length = s.length();
        boolean[][] isPalindrome = new boolean[length][length];
        int slen = 0;
        for (int i = 0; i < length; i++) {
            slen++;
            isPalindrome[i][i] = true;
        }
        for (int i = 1; i < length; i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                slen++;
                isPalindrome[i - 1][i] = true;
            }
        }

        for (int len = 3; len <= length; len++) {
            for (int i = 0; i + len <= length; i++) {
                if (s.charAt(i) == s.charAt(i + len - 1) && isPalindrome[i + 1][i + len - 2]) {
                    slen++;
                    isPalindrome[i][i + len - 1] = true;
                }
            }
        }
        return slen;
    }

    public static void main(String[] args) {
        System.out.println(countSubstrings("aaa"));
    }
}
